\documentclass{report}
\usepackage[UTF8]{ctex}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{mathrsfs} %导入花体数学字母
\usepackage{caption}
\usepackage{graphicx, subfig} %插入图片
\usepackage{listings} %插入代码
\usepackage{xcolor} %语法高亮
\usepackage{fontspec} %字体包
\usepackage{diagbox} % 斜线表头
\usepackage{geometry} %设置页面
\usepackage{enumerate}
\usepackage[colorlinks,linkcolor=blue]{hyperref} %超链接
\usepackage{marginnote} % 在正文旁边添加注释文字

\setlength{\marginparwidth}{0.6in} %页边空白处设定宽度0.6英寸
\let\oldmarginpar\marginpar
\renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize\color{red} #1]%
	{\raggedright\footnotesize\color{red} #1}} % 注释文字用红色footnote 大小
\marginparsep = 10pt %与正文间隔10pt

% \marginpar{需要添加的内容}
% 显示或隐藏页边注释，只要在文件头添加下面的语句，把它注释掉后又显示页边内容
% \renewcommand{\marginpar}[2][]{}

\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}

\usepackage{fancyhdr}
\usepackage{lipsum}
\pagestyle{fancy}

\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\sectionmark}[1]{\markright{\arabic{section}.\ #1}}
\lhead[\thepage]{\leftmark} 
\rhead[\nouppercase{\rightmark}]{\thepage}

\lstset{
	columns=fixed,       
	numbers=left,                                        % 在左侧显示行号
	numberstyle=\color{black},                       % 设定行号格式
	basicstyle=\fontspec{Consolas}\small\color[RGB]{212,212,212},
	tabsize=4,
	frame=single,                                        % 背景边框
	rulecolor=\color[rgb]{0,0,0},                  % 边框颜色
	extendedchars=false,                                 % 解决换页问题
	backgroundcolor=\color[RGB]{30,30,30},            % 设定背景颜色
	keywordstyle=\color[RGB]{156,220,254},                 % 设定关键字颜色
	identifierstyle=\color[RGB]{86,156,214},                       % 普通标识符颜色
	commentstyle=\it\color[RGB]{106,153,73},                % 设置代码注释的格式
	stringstyle=\rmfamily\slshape\color[RGB]{206,145,91},   % 设置字符串格式
	showstringspaces=false,                              % 不显示字符串中的空格
	language=c++,                                        % 设置语言
	escapeinside=``,                                     % 逃逸字符
	xleftmargin=1em,                                     % 边距设置
	xrightmargin=1em, 
	aboveskip=1em
}

\title{{\Huge Homework4\\ 数值分析}}
\author{{\LARGE 3190105815 信息与计算科学\ 行一凡}}
\date{{\LARGE \today}}

\begin{document}
	\maketitle
	\section*{Exercise I}
	\begin{equation}\label{key}
		\begin{aligned}
			477 &= (((((((1 * 2 + 1) * 2 + 1) * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 1) * 2 + 0) * 2 + 1\\ 
			&= (111011101)_2
		\end{aligned}
	\end{equation}

	\section*{Exercise II}
	\begin{equation}\label{key}
		\begin{aligned}
			\dfrac{3}{5} &= (1 + (1 + (1 + (1 + \dfrac{3}{5}) * 2^{-3}) * 2^{-1}) * 2^{-3}) * 2^{-1}\\ 
			&= (0.10011001\cdots)_2\\ 
			&= (1.00110011\cdots)_2 \times 2^{-1}
		\end{aligned}
	\end{equation}

	\section*{Exercise III}
	由$ x = 1 \times \beta^e $，则有$ x_R = (1 + 1 \times \beta^{1-p}) \times \beta^e $，从而$ x_R - x = \beta^{1-p} \times \beta^e = \beta^{e+1-p} $，而
	\begin{equation}\label{key}
		x_L = (\beta - 1) \times (1 + \beta^{-1} + \beta^{-2} + \cdots + \beta^{1-p}) \times \beta^{e-1}
	\end{equation}
	\begin{equation}\label{key}
		\begin{aligned}
			x - x_L &= (\beta - (\beta - 1) \times (1 + \beta^{-1} + \beta^{-2} + \cdots + \beta^{1-p})) \times \beta^{e-1}\\ 
			&= \left(\beta - (\beta - 1) \times \dfrac{1-\beta^{-p}}{1-\beta^{-1}}\right) \times \beta^{e-1}\\ 
			&= (\beta - (1-\beta^{-p}) \times \beta) \times \beta^{e-1}\\ 
			&= \beta^{e-p}
		\end{aligned}
	\end{equation}
	从而$ x_R - x = \beta(x - x_L) $.
	
	\section*{Exercise IV}
	\begin{equation}\label{key}
		\begin{aligned}
			\dfrac{3}{5} = (1.00110011\cdots)_2 \times 2^{-1}\\ 
			x_L = (1.0011\cdots001)_2 \times 2^{-1}\\ 
			x_R = (1.0011\cdots010)_2 \times 2^{-1}
		\end{aligned}
	\end{equation}
	且有
	\begin{equation}\label{key}
		\begin{aligned}
			x - x_L &= \dfrac{3}{5} \times 2^{-24}\\ 
			x_R - x_L &= 2^{-24}\\ 
			x_R - x &= (x_R - x_L) - (x - x_L) = \dfrac{2}{5} \times 2^{-24}
		\end{aligned}
	\end{equation}
	故$ \mathrm{fl}(x) = x_R = (1.0011\cdots010)_2 \times 2^{-1} $，
	\begin{equation}\label{key}
		\left|\dfrac{x_R-x}{x}\right| = \dfrac{2}{3} \times 2^{-24}
	\end{equation}

	\section*{Exercise V}
	机器精度$ \epsilon_M = 2^{-23} $，由于直接截断，则舍入的最大相对误差
	\begin{equation}\label{key}
		\epsilon_u = \max\left|\dfrac{\mathrm{fl}(x)-x}{x}\right| < \max\left|\dfrac{2^{-23}}{x}\right| = 2^{-23}
	\end{equation}
	从而$ \epsilon_u = 2^{-23} $
	
	\section*{Exercise VI}
	\begin{equation}\label{key}
		1 - \cos(\frac{1}{4}) \approx 0.03108\cdots
	\end{equation}
	\begin{equation}\label{key}
		\begin{aligned}
			0.015625 = 2^{-6} &< 1 - \cos(\frac{1}{4}) < 2^{-5} = 0.03125\\ 
			1 &< (1 - \cos(\frac{1}{4})) \times 2^{6} < 2
		\end{aligned}
	\end{equation}
	故精度损失6位。
	
	\section*{Exercise VII}
	\begin{enumerate}
		\item 利用 Taylor 展开，有
		\begin{equation}\label{key}
			\begin{aligned}
				1 - \cos x &= 1 - \left(1 - \dfrac{x^2}{2} + \dfrac{x^4}{4!} - \dfrac{x^6}{6!} \cdots \right)\\ 
				&= \dfrac{x^2}{2} - \dfrac{x^4}{4!} + \dfrac{x^6}{6!} - \cdots
			\end{aligned}
		\end{equation}
	
		\item 计算
		\begin{equation}\label{key}
			1 - \cos x = \dfrac{1  - \cos^{2}x}{1 + \cos x} = \dfrac{\sin^{2}x}{1 + \cos x}
		\end{equation}
	\end{enumerate}

	\section*{Exercise VIII}
	\begin{itemize}
		\item 
		\begin{equation}\label{key}
			\begin{aligned}
				C_f(x) = \left|\dfrac{x*\alpha(x-1)^{\alpha-1}}{(x-1)^{\alpha}}\right|
				= \left|\dfrac{\alpha x}{x-1}\right|
			\end{aligned}
		\end{equation}
		从而在$ x=1 $附近条件数较大。
		
		\item 
		\begin{equation}\label{key}
			C_f(x) = \left|\dfrac{x*\frac{1}{x}}{\ln x}\right| = \left|\dfrac{1}{\ln x}\right|
		\end{equation}
		从而在$ x=0 $附近条件数较大。
		
		\item 
		\begin{equation}\label{key}
			C_f(x) = \left|\dfrac{xe^{x}}{e^{x}}\right| = \left|x\right|
		\end{equation}
		从而在$ x\to\infty $时条件数较大。
		
		\item 
		\begin{equation}\label{key}
				C_f(x) = \left|\dfrac{x\frac{1}{\sqrt{1-x^{2}}}}{\arccos x}\right| = \left|\dfrac{x}{\sqrt{1-x^{2}}\arccos x}\right|
		\end{equation}
		从而在$ x=1,-1 $附近条件数较大。
	\end{itemize}

	\section*{Exercise IX}
	\begin{itemize}
		\item 已知$ x + 1 \le e^{x} $，从而
		\begin{equation}\label{key}
			C_f(x) = \left|\dfrac{xe^{-x}}{1-e^{-x}}\right| = \dfrac{x}{e^{x}-1}\le 1
		\end{equation}
		
		\item 计算$ f_A(x) $时，取$ |\delta_i|\le \epsilon_u, i = 1, 2 $得
		\begin{equation}\label{key}
			\begin{aligned}
				f_A(x) &= (1-e^{-x}(1+\delta_1))(1+\delta_2)\\ 
				&= 1 + \delta_2 - e^{-x}(1+\delta_1+\delta_2 + \delta_1\delta_2)
			\end{aligned}
		\end{equation}
		从而$ x_A = -\ln(e^{-x}(1+\delta_1+\delta_2+\delta_1\delta_2) - \delta_2) $，
		\begin{equation}\label{key}
			\begin{aligned}
				\mathrm{cond}_A(x) &= \dfrac{1}{\epsilon_u}\left|\dfrac{-\ln(e^{-x}(1+\delta_1+\delta_2 + \delta_1\delta_2) - \delta_2)-x}{x}\right|\\ 
				&\approx \dfrac{1}{\epsilon_u}\left|\dfrac{\ln(1+\delta_1+\delta_2 -\delta_2 e^{x})}{x}\right|\\ 
				&\approx \left|\dfrac{\delta_1+\delta_2-\delta_2 e^{x}}{\epsilon_u x}\right|\\ 
				&\le \left|\dfrac{2 - e^{x}}{x}\right|
			\end{aligned}
		\end{equation}
		因此$ \mathrm{cond}_A(x) $在$ [0,1] $上除$ x= 0 $附近以外都较小。
	
		\item 如图所示，出现这种情况主要是因为在计算指数函数$ e^{-x} $在 0 附近的值时，$ x $的相对误差过大
		\begin{equation}\label{key}
			\left|\dfrac{x_A-x}{x}\right| = \left|\dfrac{\ln(1+\delta)}{x}\right|
		\end{equation}
		\begin{figure}[!htb]			% 嵌套figure环境
			\centering			% 图片居中
			\includegraphics[width=0.5\textwidth]{pic/pic.png}
		\end{figure}
	\end{itemize}

	\section*{Exercise X}
	令$ \mathbf{a} = (a_0,a_1,\cdots,a_{n-1})^{T} $，根据$ q(x) $得到的函数$ f $为
	\begin{equation}\label{key}
		f(\mathbf{a}) = \sum_{i=0}^{n}a_ix^i
	\end{equation}
	条件矩阵$ A(\mathbf{a}) $是$ 1\times n $矩阵
	\begin{equation}\label{key}
		A(\mathbf{a}) = \dfrac{1}{|f(\mathbf{a})|}(|a_0|, |a_1x|, \cdots, |a_{n-1}x^{n-1}|)
	\end{equation}
	从而有
	\begin{equation}\label{key}
		\begin{aligned}
			\mathrm{cond}_f(\mathbf{a}) &= \dfrac{1}{|f(\mathbf{a})|}\parallel(|a_0|, |a_1x|, \cdots, |a_{n-1}x^{n-1}|)\parallel\\ 
			&= \dfrac{\max(|a_0|, |a_1x|, \cdots, |a_{n-1}x^{n-1}|)}{\left|\sum_{i=0}^{n}a_ix^i\right|}
		\end{aligned}
	\end{equation}

	对于 Wilkinson Example ，代入$ x = p $有
	\begin{equation}\label{key}
		\mathrm{cond}_f(\mathbf{a}) = \dfrac{\max(|a_0|, |a_1p|, \cdots, |a_{n-1}p^{p-1}|)}{\left|\sum_{i=0}^{p}a_ip^i\right|}
	\end{equation}
	\begin{equation}\label{key}
		g(x) = \prod_{k=1}^{p}(x-k) = \sum_{i=0}^{p}b_ix^i
	\end{equation}
	\begin{equation}\label{key}
		h(x) = x^{p}
	\end{equation}
	则$ g(x) + \epsilon h(x) = 0 $求根等价于
	\begin{equation}\label{key}
		\sum_{i=0}^{p}b_ix^i + \epsilon x^{p} = 0 \Leftrightarrow\sum_{i=0}^{p}c_ix^i = 0,\ c_n = 1, c_i = \dfrac{b_i}{1+\epsilon}
	\end{equation} 
	而$ g(p) + \epsilon h(p) = \epsilon p^{p} $，则有
	\begin{equation}\label{key}
		\begin{aligned}
			\mathrm{cond}_f(\mathbf{c}) &= \dfrac{\max(|c_0|, |c_1p|, \cdots, |c_{n-1}p^{p-1}|)}{(\frac{\epsilon}{1+\epsilon})p^{p}}\\ 
			&\ge \dfrac{|c_{n-1}p^{p-1}|}{(\frac{\epsilon}{1+\epsilon}) p^{p}}\\ 
			&\approx \dfrac{|b_{n-1}|}{\epsilon p}\\ 
			&= \dfrac{p+1}{2\epsilon}
		\end{aligned}
	\end{equation}
	因此，在$ x = p $附近，$ g(x) $系数的微小扰动$ (b_0,b_1,\cdots,b_{n-1})\to (c_0,c_1,\cdots,c_{n-1}) $有随$ p $增大的条件数，从而根的变化也非常大。这说明该条件数能够反映出 Wilkinson 条件中求根所需精度随多项式次数增大的问题。

	\section*{Exercise A}
	要满足$ |x-x^*| < 10^{-6} $，则区间间隔满足$ d < 2 \times 10^{-6},\ 128 = 2^7 $，而
	\begin{equation}\label{key}
		2^{-19} < 2 \times 10^{-6} < 2^{-18}
	\end{equation}
	\begin{equation}\label{key}
		(1.0000000)_2 \times 2^{7} \le x \le (1.0000001)_2 \times 2^{7}
	\end{equation}
	从而需要至少25位，至多26位精度，因此不能达到要求。
	
	\section*{Exercise B}
	由题可得
	\begin{equation}\label{key}
		\mathrm{cond}_f(x) = \dfrac{x}{\sin x}
	\end{equation}
	计算$ f_A(x) $时，取$ |\delta_i|\le \epsilon_u, i = 1, 2, 3, 4 $，忽略$ O(\delta_i^2) $得
	\begin{equation}\label{key}
		\begin{aligned}
			f_A(x) &= \dfrac{(\sin x)(1+\delta_1)}{(1+(\cos x)(1+\delta_2))(1+\delta_3)}(1+\delta_4)\\ 
			&= f(x)\dfrac{(1+\delta_1)(1+\delta_4)}{1+\delta_3}\dfrac{1+\cos x}{1 + (1+\delta_2)\cos x}\\ 
			&\approx f(x)(1+\delta_1+\delta_4)(1-\delta_3)(1-\delta_2)\dfrac{1+\cos x}{(1-\delta_2) + \cos x}\\ 
			&\approx f(x)(1+\delta_1+\delta_4-\delta_3-\delta_2)\left[1+\dfrac{\delta_2}{(1-\delta_2) + \cos x}\right]\\ 
			&\approx f(x)\left[1+\delta_1+\delta_4-\delta_3-\delta_2+\dfrac{\delta_2}{(1-\delta_2) + \cos x}\right]\\ 
			&= f(x)\left[1+\delta_1+\delta_4-\delta_3-\delta_2\dfrac{\cos x}{(1-\delta_2) + \cos x}\right]\\ 
			&\approx f(x)\left(1+\delta_1+\delta_4-\delta_3-\delta_2\dfrac{\cos x}{1 + \cos x}\right)
		\end{aligned}
	\end{equation}
	因此有$ \phi(x) = 3 + \frac{\cos x}{1 + \cos x} $，从而
	\begin{equation}\label{key}
		\mathrm{cond}_A(x)\le \dfrac{\phi(x)}{\mathrm{cond}_f(x)} = \dfrac{\sin x}{x}\left(3 + \dfrac{\cos x}{1 + \cos x}\right)
	\end{equation}
	则在$ x \to 0 $时，$ \mathrm{cond}_A(x) = \frac{7}{2} $，在区间$ (0,\frac{\pi}{2}) $上，$ \mathrm{cond}_A(x) $都较小。
	
	\section*{Code A}
	函数输出值见 res.m ，由下图比较可知$ h(x) $的计算精度更高，考虑到在 Exercise X 中的分析，这是因为前两个函数在根附近频繁加减运算，而高次多项式函数在根附近关于系数有较大的条件数，输出结果频繁波动；而$ h(x) $进行了最少次数的运算，误差更小。
	\begin{figure}[!htb]			% 嵌套figure环境
		\centering			% 图片居中
		\includegraphics[width=0.5\textwidth]{pic/f1.png}
		\caption{$ f(x) $}
	\end{figure}

	\begin{figure}[!htb]			% 嵌套figure环境
		\centering			% 图片居中
		\includegraphics[width=0.5\textwidth]{pic/f2.png}
		\caption{$ g(x) $}
	\end{figure}

	\begin{figure}[!htb]			% 嵌套figure环境
		\centering			% 图片居中
		\includegraphics[width=0.5\textwidth]{pic/f3.png}
		\caption{$ h(x) $}
	\end{figure}

	\section*{Code B}
	计算得到
	\begin{equation}\label{key}
		\mathrm{UFL}(\mathbb{F}) = 0.5,\ \mathrm{OFL}(\mathbb{F}) = 3.5
	\end{equation}
	所有的$ \mathbb{F} $中的数为
	\begin{equation}\label{key}
		0\ 0.5\ 1\ 2\ 0.625\ 1.25\ 2.5\ 0.75\ 1.5\ 3\ 0.875\ 1.75\ 3.5
	\end{equation}
	所有的$ \mathbb{F} $非正规的数为
	\begin{equation}\label{key}
		0.125\ 0.25\ 0.375
	\end{equation}
	\begin{figure}[!htb]			% 嵌套figure环境
		\centering			% 图片居中
		\includegraphics[width=0.5\textwidth]{pic/F.png}
	\end{figure}

\end{document}